import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leet16_19 {
    static int num;
    public int[] pondSizes(int[][] land) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                num = 0;
                find(land,i,j);
                if (num!=0)
                    list.add(num);
            }
        }
        int[] r = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            r[i] = list.get(i);
        }
        Arrays.sort(r);
        return r;
    }
    void find(int[][] land,int i,int j){
        if (i<0||i>=land.length||j<0||j>=land[0].length||land[i][j]!=0)
            return;
        num++;
        land[i][j] = -1;
        find(land,i+1,j);
        find(land,i-1,j);
        find(land,i,j+1);
        find(land,i,j-1);
        find(land,i+1,j+1);
        find(land,i+1,j-1);
        find(land,i-1,j+1);
        find(land,i-1,j-1);
    }

    public static void main(String[] args) {
        int[][] a = {
                {0, 2, 1, 0},
                {0, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 1, 0, 1}};
        Leet16_19 l = new Leet16_19();
        System.out.println(Arrays.toString(l.pondSizes(a)));
    }
}
